package xiaomi;

import java.util.Arrays;

/**
 * @author habitplus
 * @since 2022/8/13 11:58
 */
public class T2 {
    // 题目链接：https://xiaomi.f.mioffice.cn/docs/dock4G40Kd3yr3pBG6Qf8a1CN1b
    // 给定一个边长为n（整数）的正方形蛋糕，和一组数组，数组中的每个数代表一个小正方形蛋糕的边长，
    // 给出代码判断数组中的正方形能否可以完美拼出原正方形。
    public static void main(String[] args) {
        System.out.println(new T2().solve(4, new int[]{1,1,1,1,1,3,1,1}) ? "Yes" : "No");
        System.out.println(new T2().solve(4, new int[]{2,2,2,2}) ? "Yes" : "No");
        System.out.println(new T2().solve(5, new int[]{3,3,2,1,1,1}) ? "Yes" : "No");
    }

    private boolean solve(int n, int[] arr) {
        if (n < 1 || arr == null || arr.length < 1) return false;

        long squareSum = 0;
        int minEdge = Integer.MAX_VALUE;
        for (int e : arr) {
            minEdge = Math.min(minEdge, e);
            squareSum += (long) e * e;
        }

        if (minEdge < 1 || squareSum != (long) n * n) return false;

        // 排序
        Arrays.sort(arr);

        // 水平和垂直方向
        int hr = 0;
        int vl = 0;

        for (int i = arr.length - 1; i > 0; --i) {
            if (hr + arr[i] <= n) {
                if (vl == 0) {
                    vl = arr[i];
                }
                hr += arr[i];
                squareSum -= (long) arr[i] * arr[i];
            } else if (vl + arr[i] <= n) {
                vl += arr[i];
                squareSum -= (long) arr[i] * arr[i];
            } else {
                if (hr != n || vl != n) return false;
            }
        }

        return hr == n && vl == n;
    }
}
